/*
 * Copyright (c) 2004-2006 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Gou Pengfei
 *
 * Date:    April 2011
 */

#include "base/intmath.hh"
#include "base/bitfield.hh"
#include "cpu/edge/pred/tour_framework_exit.hh"
//#include "cpu/edge/pred/global_exit.hh"
#include "cpu/edge/pred/local_exit.hh"
#include "cpu/edge/pred/tage_exit.hh"
#include "cpu/base.hh"

template<class Impl>
TourFrameworkExit<Impl>::TourFrameworkExit(DerivEdgeCPUParams *params)
    : BaseExitPredictor<Impl>(params, "Tour"),
      choiceHistoryBits(params->choiceHistoryBits),
      choiceCtrBits(params->choiceCtrBits),
      choicePredictorSize(params->choicePredictorSize),
      blockShiftAmt(params->blockShiftAmt)
{
    initVars();

    if (params->bexitTournamentPredictionMode == "GlobalLocal") {

        DPRINTF(EdgePredUnit, "TF: global/local mode enabled.\n");
        fatal("Unimplemented GlobalLocal for exits.\n");

//        predictor1 = new GlobalExitP<Impl>(params, "AddressAndHist");
//        predictor2 = new LocalExitP<Impl>(params);

    } else if (params->bexitTournamentPredictionMode == "CPathLocal") {

        DPRINTF(EdgePredUnit, "TF: cpath/local mode enabled.\n");
        fatal("Unimplemented CPathLocal for exits.\n");

//        predictor1 = new GlobalExitP<Impl>(params, "AddressAndCPath");
//        predictor2 = new LocalExitP<Impl>(params);

    } else if (params->bexitTournamentPredictionMode == "TAGELocal") {

        DPRINTF(EdgePredUnit, "TF: tage/local mode enabled.\n");

        predictor1 = new TAGEExitP<Impl>(params);
        predictor2 = new LocalExitP<Impl>(params);

    } else {
        fatal("Invalid prediction mode selected for tournament exit"
                " predictor\n");
    }
}

template<class Impl>
TourFrameworkExit<Impl>::~TourFrameworkExit()
{
    delete predictor1;
    delete predictor2;
}

template<class Impl>
void
TourFrameworkExit<Impl>::initVars()
{
    choiceHistoryFile.resize(Impl::MaxInFlightBlockNum);
    
    for (int i = 0; i < Impl::MaxInFlightBlockNum ;++i) {
        choiceHistoryFile[i] = 0;
    }
    
    if (!isPowerOf2(choicePredictorSize)) {
        fatal("Invalid choice predictor size!\n");
    }

    /** Clear the choice history */
    for (int i = 0; i < Impl::MaxThreads; ++i) {
        choiceHistory[i] = 0;
    }

    choicePredictorMask = floorPow2(choicePredictorSize) - 1;

    /** Setup the choice history mask */
    choiceHistoryMask = (ULL(0x1) << choiceHistoryBits) - 1;
    
    /** Setup the array of counters for the choice predictor */
    choiceCtrs.resize(choicePredictorSize);

    for (int i = 0; i < choicePredictorSize; ++i) {
        choiceCtrs[i].setBits(choiceCtrBits);
    }

    DPRINTF(EdgePredUnit, "TF: chooser size: %i, mask: %#x, "
            "counter size: %i, history length: %i, "
            "history mask: %#x.\n",
            choicePredictorSize, choicePredictorMask, 
            choiceCtrBits, choiceHistoryBits, choiceHistoryMask);

    threshold = (ULL(0x1) << (choiceCtrBits - 1)) - 1;
    threshold = threshold / 2;

    exitIdBits = floorLog2(TheISA::MaxExitsInBlock);

    exitIdMask = (ULL(0x1) << exitIdBits) - 1;

    DPRINTF(EdgePredUnit, "TourFrameworkExit: exit id bits: %i"
            " exit id mask: %#x\n",
            exitIdBits, exitIdMask);
}

template<class Impl>
void
TourFrameworkExit<Impl>::reset()
{
    for (int i = 0; i < Impl::MaxInFlightBlockNum; ++i) {
        choiceHistoryFile[i] = 0;
    }
    
    //Clear the choice history
    for (int i = 0; i < Impl::MaxThreads; ++i) {
        choiceHistory[i] = 0;
    }
    
    for (int i = 0; i < choicePredictorSize; ++i) {
        choiceCtrs[i].setBits(choiceCtrBits);    
    }
}

template<class Impl>
void
TourFrameworkExit<Impl>::regStats()
{
    predictor1->regStats();
    predictor2->regStats();
}

template<class Impl>
inline
uint64_t
TourFrameworkExit<Impl>::calcChoiPredIdx(Addr &block_addr,uint64_t history)
{
    uint64_t index = history ^ (block_addr >> blockShiftAmt);

    index &= choicePredictorMask;

    return index;
}

template<class Impl>
uint64_t
TourFrameworkExit<Impl>::lookupGetIndex(Addr &block_pc, ThreadID tid)
{
    uint64_t choice_history = choiceHistory[tid] & choiceHistoryMask;
    uint64_t choice_predictor_idx = calcChoiPredIdx(block_pc, choice_history);
    return choice_predictor_idx;
}

template<class Impl>
uint64_t
TourFrameworkExit<Impl>::updateGetIndex(BlockID block_id, Addr &block_pc, ThreadID tid)
{
    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1);
    uint64_t choice_predictor_hist = choiceHistoryFile[index];
    uint64_t choice_predictor_idx = calcChoiPredIdx(block_pc, choice_predictor_hist);
    return choice_predictor_idx;
}

template<class Impl>
TheISA::ExitID
TourFrameworkExit<Impl>::lookup(BlockID block_id, BlockID oldest_block_id, 
        Addr &block_addr, int addr_space_ID, ThreadID tid)
{
    uint64_t choice_history = 0 ;
    uint64_t choice_predictor_idx = 0;
    bool choice_prediction = false;
    ExitID prediction = TheISA::MaxExitsInBlock;
    ExitID prediction_candidate_1 = TheISA::MaxExitsInBlock;
    ExitID prediction_candidate_2 = TheISA::MaxExitsInBlock;

    uint64_t choice_history_new = 0;

    prediction_candidate_1 = predictor1->lookup(block_id, oldest_block_id,
            block_addr, addr_space_ID, tid);

    prediction_candidate_2 = predictor2->lookup(block_id, oldest_block_id,
            block_addr, addr_space_ID, tid);

    //Get choice history
    choice_history = choiceHistory[tid] & choiceHistoryMask;
    choice_predictor_idx = calcChoiPredIdx(block_addr, choice_history);

    //Lookup in the choice predictor to see which one to use
    choice_prediction = (choiceCtrs[choice_predictor_idx].read() > threshold);

    // Final prediction
    prediction = choice_prediction ? prediction_candidate_1 :
                                     prediction_candidate_2;

    DPRINTF(EdgePredUnit,"TF: prediction_1 = %i, prediction_2 = %i, "
            "final prediction = %i, for %#x.\n",
            prediction_candidate_1,
            prediction_candidate_2,
            prediction,
            block_addr);

    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1); 

    // Speculative update
    choiceHistoryFile[index] = choice_history;
    choice_history_new = ((choice_history << exitIdBits) |
            (prediction & exitIdMask)) &
            choiceHistoryMask ;
    choiceHistory[tid] = choice_history_new;

    return prediction;
}

template<class Impl>
TheISA::ExitID
TourFrameworkExit<Impl>::update(BlockID block_id, Addr &block_addr, 
        int addr_space_id, ExitID actual_exit_id, ThreadID tid)
{
    uint64_t choice_predictor_hist = 0;
    uint64_t choice_predictor_idx = 0;

    assert(actual_exit_id >= 0 && actual_exit_id < TheISA::MaxExitsInBlock);

    uint64_t index = block_id & (Impl::MaxInFlightBlockNum -1);

    ExitID checked_pred_1 = predictor1->update(block_id, block_addr,
            addr_space_id, actual_exit_id, tid);

    ExitID checked_pred_2 = predictor2->update(block_id, block_addr,
            addr_space_id, actual_exit_id, tid);

    choice_predictor_hist = choiceHistoryFile[index];

    choice_predictor_idx = calcChoiPredIdx(block_addr, choice_predictor_hist);

    if (checked_pred_1 != checked_pred_2) {

        if(checked_pred_1 == actual_exit_id) {
            choiceCtrs[choice_predictor_idx].increment();
        } else if(checked_pred_2 == actual_exit_id) {
            choiceCtrs[choice_predictor_idx].decrement();
        }
    }

    DPRINTF(EdgePredUnit,"TF: actual exitID = %i, checked_pred_1= %i, "
            "and checked_pred_2 = %i.\n",
            actual_exit_id,
            checked_pred_1,
            checked_pred_2
           );

    // Useless, just keep interface unified
    return actual_exit_id;
}

template<class Impl>
void
TourFrameworkExit<Impl>::squash(BlockID block_id, Addr block_pc, 
        ExitID exit_id, ThreadID tid)
{
    uint64_t choice_history = 0;
    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1) ;

    predictor1->squash(block_id, block_pc, exit_id, tid);

    predictor2->squash(block_id, block_pc, exit_id, tid);

    choice_history = choiceHistoryFile[index];
    choiceHistory[tid] = ((choice_history << exitIdBits) |
            (exit_id & exitIdMask)) & choiceHistoryMask;

    DPRINTF(EdgePredUnit,"TF: Squashing BP to Block [bid:%i].\n", 
            block_id);
}

template<class Impl>
void
TourFrameworkExit<Impl>::squash(BlockID block_id, ThreadID tid)
{
    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1);
    uint64_t choice_history = 0;

    predictor1->squash(block_id, tid);
    predictor2->squash(block_id, tid);

    choice_history = choiceHistoryFile[index];
    choiceHistory[tid] = choice_history;
}
